package dfs;

/**
 * leet-code(79) 单词搜索
 *
 * @author Ringo
 * @date 2021/10/2 19:52
 */
public class WordsSearch {


    public static void main(String[] args) {
        char[][] board = {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        System.out.println(exist(board, "ESEE"));
    }

    public static boolean exist(char[][] board, String word) {
        int row = board.length;
        int col = board[0].length;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        boolean[][] visited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                boolean result = dfs(board, i, j, word, 0, directions, visited);
                if (result) return true;
            }
        }
        return false;
    }

    public static boolean dfs(char[][] board, int m, int n, String word, int index,
                              int[][] directions, boolean[][] visited) {
        if (board[m][n] != word.charAt(index))
            return false;
        if (index == word.length() - 1)
            return true;

        visited[m][n] = true;

        for (int[] direct : directions) {
            int a = m + direct[0], b = n + direct[1];
            if (a < 0 || b < 0 || a >= board.length || b >= board[0].length)
                continue;
            if (visited[a][b])
                continue;
            boolean result = dfs(board, a, b, word, index + 1, directions, visited);
            if (result)
                return true;
        }

        visited[m][n] = false;

        return false;
    }

}
